﻿using System;
using System.Linq;

namespace Domain
{
    public static class MergeSort
    {
        public static int[] Sort(int[] array)
        {
            if (array == null)
                throw new Exception("Array is null");

            if (array.Length == 0)
                return array;

            int arrayLength = array.Length;

            if (arrayLength == 1)
                return array;

            int middle = arrayLength/2;

            int[] sortedLeftHalf = Sort(array.Take(middle).ToArray());
            int[] sortedRightHalf = Sort(array.Skip(middle).ToArray());

            int[] mergedArray = Merge(sortedLeftHalf, sortedRightHalf);
            
            return mergedArray;
        }

        private static int[] Merge(int[] leftHalf, int[] rightHalf)
        {
            int arrayLength = leftHalf.Length + rightHalf.Length;
            int[] mergedArray = new int[arrayLength];

            int leftIndex = 0;
            int rightIndex = 0;
            
            for (int i = 0; i < arrayLength; i++)
            {
                if (LeftElementToWrite(leftHalf, rightHalf, leftIndex, rightIndex))
                {
                    mergedArray[i] = rightHalf[rightIndex];
                    rightIndex++;
                }
                else
                {
                    mergedArray[i] = leftHalf[leftIndex];
                    leftIndex++;
                }
            }

            return mergedArray;
        }

        private static bool LeftElementToWrite(int[] leftHalf, int[] rightHalf, int leftIndex, int rightIndex)
        {
            return ((leftIndex == leftHalf.Length) || ((rightIndex < rightHalf.Length) && (rightHalf[rightIndex] < leftHalf[leftIndex])));
        }
    }
}
